The present invention relates generally to computer graphics systems using mesh representations of three-dimensional objects, and more particularly to improved mesh simplification techniques. Still more particularly, the present invention relates to an edge collapse transformation employing a new quadric error metric (QEM) for use in determining the geometric position of a new vertex created by the edge collapse, the values of appearance attributes associated with the new vertex, and the order in which edges are collapsed.
In a computer graphics system, it is desirable to represent an object as efficiently as possible to preserve memory and system bandwidth, and to enhance rendering speed. Computer graphics, such as in computer generated images, animations and effects for motion pictures, television, computer multi-media, computer games, print and other media, often employ detailed geometric models for rendering images of three-dimensional (3D) objects. These models are typically created using commercially available computer-aided modeling and 3D scanning systems. Although some geometric models may be initially defined using high level primitives, for efficient rendering they are typically converted to their lowest common denominator form, polygonal approximations called meshes.
In the simplest case, a mesh consists of a set of vertices and a set of faces. Each vertex specifies the (x, y, z) coordinates of a point in space, and each face defines a polygon by connecting together an ordered subset of the vertices. These conjoined polygons approximate the surface geometry of the modeled object. The polygons may in general have arbitrary numbers of vertices (and even holes). For convenience, the special case of a mesh (called a xe2x80x9ctriangle meshxe2x80x9d) in which all faces have exactly three vertices is commonly used. Arbitrary meshes composed of polygons having faces with any number of vertices equal to or greater than three can be easily converted to triangle meshes through known triangulation processes. Complex triangle meshes occur extensively in computer graphics as the result of geometric modeling operations, global illumination simulations, and reconstructions from 3D scans.
In the following discussion, the geometry of a triangle mesh is denoted by a tuple (K,V), where K is a simplicial complex specifying the connectivity of the mesh simplices (i.e., the adjacency of the vertices, edges, and faces), and V={vl, . . . , vm} is the set of vertex positions vj=(xj,yj,zj) defining the shape of the mesh in R3. (See, e.g., Hoppe et al., Mesh Optimization, Computer Graphics (SIGGRAPH ""93 Proceedings) (1993), 19-26 (hereinafter referred to as Hoppe93)). An exemplary mesh 80 is shown in FIG. 1. The vertices of a triangle mesh (e.g., vertices 82-89 of the mesh 80) are denoted as vl, . . . , vm; the edges (e.g., 92-95) are denoted by pairs of adjacent vertices as e={vj,vk}; and the faces (e.g., faces 100-107) are denoted by triples of interconnected vertices as f={vj,vk,vl}.
Complex (i.e., highly detailed) triangle meshes are notoriously difficult to render, store, and transmit. The meshes created by modeling and scanning systems are typically not optimized for display performance. In most applications, these initial meshes can usually be replaced by nearly indistinguishable approximations with far fewer faces, thereby improving rendering efficiency. One approach to speed up rendering is to replace a complex mesh by a set of level-of-detail (LOD) approximations. A detailed mesh is used when the object is close to the viewer, and coarser approximations (i.e., meshes with fewer vertices and faces) are substituted as the object recedes from the viewer in the image. These LOD approximations can be precomputed automatically using known mesh simplification methods. Thus, a fully detailed mesh is used when the object is close, and coarser approximations are substituted as the object recedes.
Because such meshes are difficult to store, transmit, and render, several techniques have been developed for geometrically simplifying them (see, e.g., Garland and Heckbert, Surface Simplification Using Quadric Error Metrics, Computer Graphics (SIGGRAPH ""97 Proceedings) (1997), 209-216 (hereinafter referred to as Garland97); and Hoppe, Progressive Meshes, Computer Graphics (SIGGRAPH ""96 Proceedings) (1996), 99-108 (hereinafter referred to as Hoppe96), both of which are incorporated herein by reference). Recent geometric simplification schemes coarsen a mesh through a sequence of edge collapse transformations 110, as shown in FIG. 1. These transformations have the advantage that their inverses can be stored concisely to form a progressive mesh representation as described in Hoppe96. Moreover, co-pending application titled Progressive Meshes, U.S. patent application Ser. No. 08/586,953, filed Jan. 11, 1996, commonly assigned and incorporated herein by reference (hereinafter referred to as Hoppe""953), describes a progressive mesh (PM) representation which provides a unified solution to the problems of efficiently storing, transmitting and rendering a mesh of arbitrary complexity. In short, the PM representation of an arbitrary mesh M is stored as a coarse or base mesh M0 together with a sequence of n refinement records that indicate how to incrementally refine M0 back up to the arbitrary mesh M. Each refinement record encodes information associated with a vertex split transformation 116 that transforms the mesh by splitting a vertex 86xe2x80x2 or vs (positioned between side vertices vl and vr) to add one vertex 89 or vt and up to two faces (fl={vs, vt, vl} and fr={vs, vt, vr}) to the mesh. The PM representation thus defines a continuous sequence of LOD approximations to the arbitrary mesh that are produced by applying the vertex split transformation defined by successive refinement records successively to the base mesh M0, resulting in a sequence of progressively more detailed meshes M0 . . . Mn, Mn=M. In other words, the PM representation of M thus defines a continuous sequence of meshes M0,M1, . . . ,Mn of increasing accuracy from which LOD approximations with a desired complexity can be efficiently retrieved.
Thus, FIG. 1 shows the vertex split transformation 116 and its inverse, the edge collapse transformation 110. As shown in FIG. 1, each edge collapse transformation unifies two adjacent vertices into one (e.g., vertex 86xe2x80x2 in mesh 112), thereby removing two faces (100 and 101) from the mesh. For the purpose of level-of-detail control, edge collapses are selected to best preserve the appearance of the mesh during simplification. Several appearance metrics have been developed and are described in, for example, Cohen et al., Appearance-Preserving Simplication, Computer Graphics (SIGGRAPH ""98 Proceedings) (1998), 115-122; Garland97; and Hoppe96.
In a simplification scheme based on edge collapses, two issues are to be addressed: (1) the position and attributes values v to assign to the unified, or new, vertex vs 86"", and (2) the order in which to perform edge collapses. A common approach is to define a single cost metric C to determine both. The unified vertex is assigned the value v that minimizes C(v), and the same cost C(v) is used to order the candidate edge collapses. Previous approaches to defining C(v) are described below.
Gueziec, Surface Simplification With Variable Tolerance, Proceedings of the Second International Symposium on Medical Robotics and Computer Assisted Surgery (November 1995), 132-139, constrains edge collapses to preserve mesh volume, and bounds the maximum geometric approximation error through a framework of tolerance volumes. Hoppe93 and Hoppe96 sample a set of points on the original mesh, and define C(v) as the sum of their squared distances to the approximating mesh. One drawback is that the subset of points that must be reprojected grows as the mesh is simplified. Kobbelt et al., A General Framework For Mesh Decimation, Proceedings of Graphics Interface ""98 (1998), also sample points on the original mesh, but constrain their maximum distance to the approximating mesh, and use a fairness functional to order the edge collapses.
Ronfard and Rossignac, Full-Range Approximation Of Triangulated Polyhedra, Computer Graphics Forum (Proceedings of Eurographics ""96) 15, 3 (1996), 67-76, associate to each original vertex the set of planes spanned by its adjacent faces, merge these sets of planes after each edge collapse, and define C(v) as the sum of squared distances from v to its associated planes. Again, a drawback is that these plane sets grow as the mesh is simplified. Garland97 shows that this same C(v) can be efficiently represented as a compact quadric error metric.
Lindstrom and Turk, Fast And Memory Efficient Polygonal Simplification, Visualization ""98 Proceedings (1998), IEEE, 279-286, define C(v) as a sum of squared tetrahedral volumes between the two mesh neighborhoods of FIG. 1. Specifically, each tetrahedron is formed by the vertex vs 86xe2x80x2 and a face f of the mesh 80. Because each tetrahedral volume is proportional to the distance of vs from the plane spanning f, the metric C(v) can be seen as an instance of a QEM over the neighborhood of mesh 80 where the metric on each face f of the mesh 80 is weighted by the squared area of f. A major difference from the earlier scheme of Garland97 is that the error metric is defined over the mesh simplified so far instead of the original mesh. This is referred to as the memoryless version of QEM simplification. Lindstrom and Turk also use constraints to preserve volume and boundaries.
Other techniques allow modification to a topological type of the mesh through a more general vertex unification transformation (see, e.g., Popovic and Hoppe, Progressive Simplicial Complexes, Computer Graphics (SIGGRAPH ""97 Proceedings) (1997), 217-224; and Schroeder, A Topology Modifying Progressive Decimation Algorithm, Visualization ""97 Proceedings (1997), IEEE, 205-212.
For realistic rendering of an object, meshes in computer graphics (including the continuous sequence of LOD meshes defined by the PM representation) often have numerous other appearance attributes in addition to their geometric properties (i.e., vertex positions and connectivity of vertices and polygons). These additional appearance attributes can be classified into two types, discrete attributes and scalar attributes.
The discrete attributes arc usually associated with faces of the mesh. A common discrete attribute, the material identifier, determines the shader function used in rendering each face of the mesh. For instance, a trivial shader function may involve a straightforward look-up in a specified texture bitmap.
Many scalar attributes usually also are associated with a mesh. In general, the scalar attributes specify local parameters of the shader functions defined on the mesh faces. Typical examples include texture coordinates and normals that in simple cases are associated with vertices of the mesh. In the case of a simple shader function that projects a bitmap onto a face of the mesh (e.g., the texture bitmap specified by the discrete attribute associated with the face), texture coordinates that are represented as value pairs (u,v) and associated with the vertices of the face indicate locations in the text bitmap that project onto the respective vertices. Normals that indicate a direction perpendicular to the face at the vertex, such as with a value set (nx, ny, nz), may be used for more complex shading and/or lighting effects. Thus, meshes often have associated appearance attributes at their vertices, such as normals, colors, and texture coordinates. It should be noted that relatively few techniques account for these attributes during simplification.
Among mesh simplification metrics, the quadric error metric introduced by Garland97 is both fast and reasonably accurate. The more recent work, Garland and Heckbert, Simplifying Surfaces With Color And Texture Using Quadric Error Metrics, Visualization ""98 Proceedings (1998), IEEE, 263-269 (hereinafter referred to as Garland98) generalizes this approach to deal with appearance attributes, and is incorporated herein by reference.
Bajaj and Schikore, Error-Bounded Reduction Of Triangle Meshes With Multivariate Data, SPIE 2656 (1996), 34-45, track geometric and attribute errors on faces of the mesh to obtain error-bounded simplifications of meshes with attributes. Hoppe96 extends the point sampling approach to include attributes in the cost metric, but decouples geometric optimization from attribute optimization when minimizing C(v). Garland98 generalizes the QEM scheme of Garland97 to deal with surface properties. The present invention is directed to another, more intuitive generalization that is more accurate and efficient.
Cohen et al. simplify meshes with explicit texture coordinates. By tracking parametric instead of geometric correspondence, their scheme bounds the displacement of a point on the mesh with any given texture coordinate, which is the preferred metric for texture-mapped surfaces. The present invention seeks to minimize the attribute deviation at any given point on the surface. This is the correct metric for vertex attributes like colors and normals that do not define a parametrization on the surface.
There are applications involving computer graphics in which it is necessary or desirable to provide efficient and accurate geometric simplification of meshes. Accordingly, a goal of the present invention is to provide an improved error metric for use in carrying out mesh simplification, and particularly edge collapse, transformations of the kind discussed above.
The present invention provides systems and methods for determining a quadric error metric for use in determining the positions of new vertices created by edge collapse transformation, the values of appearance attributes associated with such new vertex, and the order in which edges are collapsed. The appearance attributes may include normals, colors, and/or texture coordinates.
In accordance with the present invention, the quadric error metric may be minimized to determine the most desirable position and attribute values for each new vertex. Both the geometric position of the vertex 86xe2x80x2 and its attributes are determined simultaneously. Indeed, the attribute field over the mesh neighborhood 80 can affect the position of the unified vertex 86xe2x80x2. For example, one can consider the case in which the neighborhood 80 is completely planar. In that case, the position p of the unified vertex 86xe2x80x2 can lie anywhere in the plane and still give rise to zero geometric error. However, the attribute field over the mesh 80 may have a sharp gradient, which influences the position of the vertex.
A geometric error as a function of the vertex position p is created in the form of a QEM represented by (A,b,c) coefficients. Then, an attribute error as a function of both vertex position p and attributes s is created in the form of another QEM. These QEM""s are defined initially for each face f 100-107 and then summed. Thus the final QEM for the vertex v=(p,s) 86xe2x80x2 is the sum over all faces 100-107 and over both geometric error and attribute errors.
Having formed this one summed QEM (by summing up the corresponding coefficients in the (A,b,c) representations of the individual QEM""s), its minimum is computed; that is, the position p and attributes s for vertex 86xe2x80x2 that minimize the QEM are obtained.
The inventive quadric error metric is the sum of the geometric error and the attribute error. The geometric error may be defined as the sum of the squared distances from a point in space (the new vertex) to each of the closest points on the planes associated with the collapsed edge, where the associated planes are the planes spanned by the faces adjacent to the collapsed edge. The attribute error is itself a function the geometric position of the new vertex, and may be represented by a relatively sparse matrix comprising an mxc3x97m identity matrix, which provides improved computational efficiency.
Additional features and advantages of the invention will be made apparent from the following detailed description of an illustrated embodiment.